\chapter{Intermediate representation}
\label{chap-ir}

\section{Instruction graph}

The compiler translates an abstract syntax tree into a \emph{graph} of
\emph{instructions}.

This graph is a variation on a \emph{control flow graph}.  As such, it
has a unique instruction called the \emph{initial instruction} which
is the instruction where the execution of the program starts.

In general an instruction can have zero, one, or more
\emph{successors}, and zero, one, or more \emph{predecessors}.

An instruction can also have zero, one, or several \emph{inputs} and
zero, one, or more \emph{outputs}.  An input may be an \emph{constant}
value or a \emph{location} (also called a ``variable'').%
\footnote{The only exception to this rule is that an
  \texttt{enclose-instruction} has an \texttt{enter-instruction} as
  its input.}  An output may only be a location.

There are two types of location: \emph{lexical} locations and
\emph{values} locations. The former is used for most instructions,
while the latter represents collections of an unknown number of
\commonlisp{} values, as output for example by \texttt{funcall} in
general.

The execution of an instruction consists of generating the outputs as
a function of the inputs, and also of choosing a successor based on
the inputs.

The execution of a program consists of starting execution at the
\emph{initial instruction} and executing a sequence of instructions
where an instruction in the sequence is the successor chosen during
the execution of the preceding instruction in the sequence.

An instruction graph is said to be \emph{well formed} if and only if
the restrictions on each of the instructions are respected, as defined
in \refSec{sec-ir-instructions}.

It is possible for a well-formed instruction graph to contain
instructions that are not \emph{reachable} in that there is no
execution path from the initial instruction to such an instruction.
This situation can arise as a result of certain optimizations that
determine that a particular successor arc of some instruction can
never be chosen, and so removes that arc.  In certain cases, the
instruction at the head of that arc may then not be reachable from the
initial instruction.

Because of the existence of \texttt{enclose-instruction}s, the concept
of reachability is actually a bit more complicated than what was
hinted in the previous paragraph.  More formally, an instruction is
reachable if and only if:

\begin{itemize}
\item it is an \texttt{enter-instruction}, or
\item it has a reachable predecessor.
\end{itemize}

By stating that every \texttt{enter-instruction} is reachable a
priori, we implicitly assume that the closure generated as the output
of every \texttt{enclose-instruction} is actually \emph{used}.
Whether this is the case or not is of course \emph{undecidable}, but
the translation from an abstract syntax tree to an instruction graph
eliminates some of the cases where the closure may not be used, in
that it does not generate output for anonymous functions that are
evaluated in a context where the resulting closure is obviously not
needed.

An instruction graph program is said to be \emph{reduced} if and only
if it is \emph{well formed} and every instruction is \emph{reachable}.

\section{Instruction and data ownership}

Recall that an \texttt{enter-instruction} is the successor of no other
instruction.

The \texttt{enter-instruction}s of a program constitute a directed
tree.  An \texttt{enter-instruction} $I$ closer to the root of the
tree than some other \texttt{enter-instruction} $J$ is said to be
located \emph{further out} than $J$.

The \texttt{enter-instruction}s of the tree correspond directly to the
functions in the source code.  Some of these functions are introduced
by \texttt{flet} or \texttt{labels}, and some are anonymous and
introduced by \texttt{lambda}.  Yet some are introduced by
\texttt{let} or \texttt{let*}, which are considered syntactic sugar
for functions.

Each instruction is generated as a result of compiling a particular
function.  The \texttt{enter-instruction} corresponding to that
function is called the \emph{owner} of the instruction.  Ownership is
transitive, in that the successor $J$ of some instruction $I$ has the
same owner as $I$.

The owner of a datum $D$ is the outermost \texttt{enter-instruction}
of all the owners of all the instructions using $D$.

Each \texttt{enter-instruction} $E$ defines a \emph{procedure} which
is a the set of all the instructions owned by $E$.  We extend the
definition of ownership so that a procedure $P$ is the owner of some
instruction or datum $X$ if an only if the unique
\texttt{enter-instruction} of $P$ is the owner of $X$.

\section{Levels of detail}

From its initial creation, the instruction graph is transformed in
various ways.  A transformation may add or delete instructions, alter
the predecessor/successor relationship between instructions, or add or
delete inputs or outputs.

Furthermore, some transformations may add new \emph{types} of
instructions that were not present before, and some transformations
may remove all instructions of a particular type.

Globally speaking, however, the instruction graph comes in two major
varieties defined by what types of instructions it contains.  These
two varieties are called \emph{High-level Intermediate Representation}
(or HIR) and \emph{Medium-level Intermediate Representation} (or MIR)
respectively.

\subsection{High-level Intermediate Representation}

At the HIR level, no address calculations are exposed.  All variables
contain \commonlisp{} objects, except that some variables may contain
\emph{unboxed} or \emph{raw} versions of such objects, in particular
integers, floating-point numbers, and characters.

Argument parsing is not exposed, and is instead hidden in a single
\texttt{enter-instruction}.  Similarly, the details of how functions
are called and how values are returned is hidden.  Instructions exist
for accessing the slots of a \texttt{cons} cell, the elements of an
array, and the slots of a standard instance.

The main purpose of restricting the contents variables to
\commonlisp{} objects is that it makes \emph{type inference}
possible.

\subsection{Medium-level Intermediate Representation}

MIR differs from HIR in that real implementation-specific and
backend-specific details are introduced.  The instructions for
accessing slots of a \texttt{cons} cell, elements of an array, or
slots of a standard object, are expanded to expose tagging and address
calculations.

This is the level where most traditional optimizations are
accomplished, such as \emph{value numbering}, \emph{redundancy
  elimination}, \emph{common subexpression elimination}, etc.

\subsection{Low-level Intermediate Representation}

At this level, \emph{registers} and \emph{stack locations} are
introduced according to the conventions for the implementation and the
backend.

This is the level where \emph{register allocation} is accomplished.

\subsection{Compilation policy}

All instructions include a compilation policy \seechap{chap-policy},
specified by the initarg \texttt{:policy} and with accessor
\texttt{policy}. If many instructions are being created at once, the
special variable \texttt{*policy*} can be bound, and will be used
as an initform.

\section{Definition of instructions}
\label{sec-ir-instructions}

\subsection{Instruction \texttt{enter-instruction}}
\label{hir-instruction-enter}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 0\\
\hline
Number of outputs & any\\
\hline
Number of predecessors & 0\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

An instruction of this type is the initial instruction of an
instruction graph.  It is also an input to an
\texttt{enclose-instruction}.  The outputs of this instruction
corresponds to the parameters the function as follows:

\begin{itemize}
\item There is an output for every required parameter.
\item For each optional parameter and for each keyword parameter,
  there are two outputs, one for the parameter itself and one for the
  \texttt{supplied-p} parameter.
\end{itemize}

The execution of this instruction involves parsing the arguments given
to the function, and setting the outputs accordingly.  

The \texttt{enter-instruction} has an accessor named
\texttt{lambda-list}.  The lambda list of this instruction resembles
an ordinary lambda list in that it has a number of required
parameters, possibly a \texttt{\&rest} parameter and some
\texttt{\&optional} and \texttt{\&key} parameters.  It differs from an
ordinary lambda list in the following way:

\begin{itemize}
\item Each required parameter is a \texttt{lexical-location} which is
  also one of the outputs of the instruction.
\item If the \texttt{\&rest} lambda list keyword is present, it is
  followed by a \texttt{lexical-location} which is also one of the
  outputs of the instruction.
\item If the \texttt{\&optional} lambda list keyword is present, it is
  followed by any number of two-element lists.  Each element of each
  such lists is a \texttt{lexical-location} which is also one of the
  outputs of the instruction.  The first element represents the
  argument if it was given and the second element represents a
  \texttt{supplied-p} argument containing either \texttt{nil} or
  \texttt{t}.
\item If the \texttt{\&key} lambda list keyword is present, it is
  followed by any number of three-element lists.  The first element of
  each such list is a \emph{symbol} (typically a symbol in the
  \texttt{keyword} package) used to recognize whether the
  corresponding argument has been given.  The second element and the
  third element of each list is a \texttt{lexical-location} which is
  also one of the outputs of the instruction.  The second element
  represents the argument if it was given and the third element
  represents a \texttt{supplied-p} argument containing either
  \texttt{nil} or \texttt{t}.
\item It does not have any \texttt{\&aux} parameters.
\end{itemize}

Notice that the outputs are lexical locations independently of whether
the parameters to the function are special variables.  The
instructions following the \texttt{enter-instruction} are responsible
for binding special variables and assigning default values to
unsupplied \texttt{\&optional} and \texttt{\&key} parameters.

\subsection{Instruction \texttt{nop-instruction}}
\label{hir-instruction-nop}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 0\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

Executing this instruction has no effect.  This instruction may be
introduced by certain transformations as a replacement for existing
instructions.  This way, these transformations do not have to be
concerned with complex updates of the graph.  Instead a dedicated
transformation for removing all \texttt{nop-instruction}s is provided.

\subsection{Instruction \texttt{assignment-instruction}}
\label{hir-instruction-assignment}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The execution of this instruction results in the input being copied to
the output without any modification. 

\subsection{Instruction \texttt{funcall-instruction}}
\label{hir-instruction-funcall}

\begin{tabular}{|l|l|}
\hline
Number of inputs & any\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input of this instruction corresponds to the function being
called.  The remaining inputs correspond to the arguments to be passed
to the callee.

The values resulting from the call are stored in the global values
location.

\subsection{Instruction \texttt{funcall-no-return-instruction}}
\label{hir-instruction-funcall-no-return}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & any\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 0\\
  \hline
\end{tabular}

This instruction is identical to \texttt{funcall-instruction}, except
that the function called is known to execute a non-local control
transfer rather than return normally, e.g. by \texttt{throw} or
\texttt{error}. As such, this instruction has no successors or output.

Use of this instruction rather than \texttt{funcall-instruction}
simplifies analysis of programs, as impossible control paths need not
be analyzed.

\subsection{Instruction \texttt{tailcall-instruction}}
\label{hir-instruction-tailcall}

\begin{tabular}{|l|l|}
\hline
Number of inputs & any\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 0\\
\hline
\end{tabular}

The first input of this instruction corresponds to the function being
called.  The remaining inputs correspond to the arguments to be passed
to the callee.

This instruction can be used instead of a \texttt{funcall-instruction}
immediately followed by a \texttt{return-instruction} such that the
output of the \texttt{funcall-instruction} is the input of the
\texttt{return-instruction}.

\subsection{Instruction \texttt{return-instruction}}
\label{hir-instruction-return}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 0\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 0\\
\hline
\end{tabular}

This instruction takes its values from the global values location,
which is why it has no inputs.

It terminates execution of the current function and returns to the
caller. 

\subsection{Instruction \texttt{enclose-instruction}}
\label{hir-instruction-enclose}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The input of this instruction is different from those of other
instructions because it is another instruction, namely an
\texttt{enter-instruction}.

The instruction takes the instruction graph of the input and creates a
\emph{closure}.  The closure contains the current lexical runtime
environment and the code resulting from the input instruction graph.

\subsection{Instruction \texttt{fdefinition-instruction}}
\label{hir-instruction-fdefinition}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 1\\
  \hline
  Number of outputs & 1\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

The input is either a constant input, or a lexical location holding a
function name. The output is the function with that name in the global
environment.

\subsection{Instruction \texttt{eq-instruction}}
\label{hir-instruction-eq}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The inputs to this instruction are two arbitrary \commonlisp{}
objects.  The first successor is chosen if the values of the inputs
are identical.  Otherwise, the second successor is chosen.

\subsection{Instruction \texttt{consp-instruction}}
\label{hir-instruction-car}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The input to this instruction can be any object.  The instruction
tests whether the input is a \texttt{cons} cell.  If it is, then the
first successor is chosen.  Otherwise, the second successor is chosen.

Normally, this instruction would not be present at the HIR level.
Instead, the more general \texttt{typeq-instruction}
\seesec{hir-instruction-typeq} would be used.  But when HIR is
translated to MIR, then the \texttt{typeq-instruction} is eliminated
in an implementation-specific way.  Implementations that have a simple
way of testing whether an object is a \texttt{cons} cell can then turn
a \texttt{typeq-instruction} with a type of \texttt{cons} into a
\texttt{consp-instruction}.

\subsection{Instruction \texttt{car-instruction}}
\label{hir-instruction-car}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The input to this instruction must be a \texttt{cons} cell. The
consequences are undefined if this is not the case.  For that reason,
\emph{safe} code should have additional instructions inserted to
ensure that this condition is respected.  The output is the contents
of the \texttt{car} of the \texttt{cons} cell.

\subsection{Instruction \texttt{cdr-instruction}}
\label{hir-instruction-cdr}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The input to this instruction must be a \texttt{cons} cell. The
consequences are undefined if this is not the case.  For that reason,
\emph{safe} code should have additional instructions inserted to
ensure that this condition is respected.  The output is the contents
of the \texttt{cdr} of the \texttt{cons} cell.

\subsection{Instruction \texttt{rplaca-instruction}}
\label{hir-instruction-rplaca}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input to this instruction must be a \texttt{cons} cell.  The
consequences are undefined if this is not the case.  For that reason,
\emph{safe} code should have additional instructions inserted to
ensure that this condition is respected.  The second input can be any
object.  The effect of the instruction is to replace the contents of
the \texttt{car} of the \texttt{cons} cell by the second input.

\subsection{Instruction \texttt{rplacd-instruction}}
\label{hir-instruction-rplacd}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input to this instruction must be a \texttt{cons} cell.  The
consequences are undefined if this is not the case.  For that reason,
\emph{safe} code should have additional instructions inserted to
ensure that this condition is respected.  The second input can be any
object.  The effect of the instruction is to replace the contents of
the \texttt{cdr} of the \texttt{cons} cell by the second input.

\subsection{Instruction \texttt{nook-read-instruction}}
\label{hir-instruction-nook-read}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input to this instruction must be a \emph{standard object},
or some other object with the same structure as a standard object.
The consequences are undefined if this is not the case.  For that
reason, \emph{safe} code should have additional instructions inserted
to ensure that this condition is respected.  The second input is a
non-negative fixnum indicating the \emph{index} of the nook in the
instance.  The output is the contents of the corresponding nook.

\subsection{Instruction \texttt{nook-write-instruction}}
\label{hir-instruction-nook-write}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 3\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input to this instruction must be a \emph{standard object},
or some other object with the same structure as a standard object.
The consequences are undefined if this is not the case.  For that
reason, \emph{safe} code should have additional instructions inserted
to ensure that this condition is respected.  The second input is a
fixnum indicating the \emph{index} of the nook in the instance.  The
third input can be any object.  The effect of the instruction is to
replace the contents of the corresponding nook by the third input.

\subsection{Instruction \texttt{aref-instruction}}
\label{hir-instruction-aref}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has two additional slots, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:element-type} & \texttt{element-type} & Upgraded array element type of array inputs.\\
  \hline
  \texttt{:simple-p} & \texttt{simple-p} & The actual simplicity of array inputs.\\
  \hline
\end{tabular}

The first input to this instruction must be an array with actual
element type and actual simplicity corresponding to that specified in
the instruction slots. The consequences are undefined if this is not
the case.  For that reason, \emph{safe} code should have additional
instructions inserted to ensure that this condition is respected.  The
second input is a non-negative fixnum indicating the \emph{row-major
  index} of an element of the array.  The output is the contents of
the corresponding element of the array.

The output may be \emph{unboxed}, depending on the implementation
and element-type.  If the output is unboxed, it must be used only in
contexts where values of this type are permitted.

\subsection{Instruction \texttt{aset-instruction}}
\label{hir-instruction-aset}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 3\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction has two additional slots, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:element-type} & \texttt{element-type} & Upgraded array element type of array inputs.\\
  \hline
  \texttt{:simple-p} & \texttt{simple-p} & The actual simplicity of array inputs.\\
  \hline
\end{tabular}

The first input to this instruction must be an array with actual
element type and actual simplicity corresponding to that specified
in the instruction slots. The consequences are undefined if this is
not the case.  For that reason,
\emph{safe} code should have additional instructions inserted to
ensure that this condition is respected.
 safe code should insert additional instructions to
ensure it. The second input is a non-negative fixnum indicating the
\emph{row-major index} of an element of the array. The third input
is the object to be written into the array. There are no outputs.

The object to be written into the array may be \emph{unboxed}, depending
on the implementation and element-type.

\subsection{Instruction \texttt{fixnump-instruction}}
\label{hir-instruction-car}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The input to this instruction can be any object.  The instruction
tests whether the input is a \texttt{fixnum}.  If it is, then the
first successor is chosen.  Otherwise, the second successor is chosen.

Normally, this instruction would not be present at the HIR level.
Instead, the more general \texttt{typeq-instruction}
\seesec{hir-instruction-typeq} would be used.  But when HIR is
translated to MIR, then the \texttt{typeq-instruction} is eliminated
in an implementation-specific way.  Implementations that have a simple
way of testing whether an object is a \texttt{fixnum} can then turn
a \texttt{typeq-instruction} with a type of \texttt{fixnum} into a
\texttt{fixnump-instruction}.

\subsection{Instruction \texttt{fixnum-add-instruction}}
\label{hir-instruction-fixnum-add}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1 or 2\\
\hline
\end{tabular}

The inputs to this instruction must be of type \texttt{fixnum}.  If
the program is \emph{safe}, then control must reach this instruction
only if this restriction is verified.  The output is a
\texttt{fixnum}.

When there are two successors, if the first successor is chosen, then
the output is the sum of the two inputs.

If the second successor is chosen, then the sum of the inputs is not
possible to represent as a fixnum, so in order to obtain the sum of
the two inputs, the following adjustment has to be made:

\begin{itemize}
\item If the output is negative, then $2^n$ must be added to the
  output, where $n$ is the number of bits used to represent a fixnum. 
\item If the output is positive, then $2^n$ must be subtracted from
  the output, where $n$ is the number of bits used to represent a
  fixnum.
\end{itemize}

The second successor is typically a \texttt{funcall-instruction} to
some function that accomplishes this adjustment and returns a bignum.

If there is a single successor, overflow is not tested for.

\subsection{Instruction \texttt{fixnum-sub-instruction}}
\label{hir-instruction-fixnum-sub}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The inputs to this instruction must be of type \texttt{fixnum}.  If
the program is \emph{safe}, then control must reach this instruction
only if this restriction is verified.  The output is a
\texttt{fixnum}.

If the first successor is chosen, then the output is the difference
between the two inputs.

If the second successor is chosen, then the difference between the
inputs is not possible to represent as a fixnum, so in order to obtain
the difference between the two inputs, the following adjustment has to
be made:

\begin{itemize}
\item If the output is negative, then $2^n$ must be added to the
  output, where $n$ is the number of bits used to represent a fixnum. 
\item If the output is positive, then $2^n$ must be subtracted from
  the output, where $n$ is the number of bits used to represent a
  fixnum.
\end{itemize}

The second successor is typically a \texttt{funcall-instruction} to
some function that accomplishes this adjustment and returns a bignum.

\subsection{Instruction \texttt{fixnum-less-instruction}}
\label{hir-instruction-fixnum-less}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The inputs to this instruction must be of type \texttt{fixnum}.  If
the program is \emph{safe}, then control must reach this instruction
only if this restriction is verified.

The first successor is chosen if and only if the first input is
strictly less than the second input.

\subsection{Instruction \texttt{fixnum-not-greater-instruction}}
\label{hir-instruction-fixnum-le}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The inputs to this instruction must be of type \texttt{fixnum}.  If
the program is \emph{safe}, then control must reach this instruction
only if this restriction is verified.

The first successor is chosen if and only if the first input is
less than or equal to the second input.

\subsection{Instruction \texttt{fixnum-equal-instruction}}
\label{hir-instruction-fixnum-equal}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The inputs to this instruction must be of type \texttt{fixnum}.  If
the program is \emph{safe}, then control must reach this instruction
only if this restriction is verified.

The first successor is chosen if and only if the first input is equal
to the second input.

\subsection{Instruction \texttt{characterp-instruction}}
\label{hir-instruction-car}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

The input to this instruction can be any object.  The instruction
tests whether the input is a \texttt{character}.  If it is, then the
first successor is chosen.  Otherwise, the second successor is chosen.

Normally, this instruction would not be present at the HIR level.
Instead, the more general \texttt{typeq-instruction}
\seesec{hir-instruction-typeq} would be used.  But when HIR is
translated to MIR, then the \texttt{typeq-instruction} is eliminated
in an implementation-specific way.  Implementations that have a simple
way of testing whether an object is a \texttt{character} can then turn
a \texttt{typeq-instruction} with a type of \texttt{character} into a
\texttt{characterp-instruction}.

\subsection{Instruction \texttt{phi-instruction}}
\label{hir-instruction-phi}

\begin{tabular}{|l|l|}
\hline
Number of inputs & > 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction is used for variables respecting the \emph{static
  single assignment} (SSA) property.  

One of the following must hold for any \texttt{phi-instruction} A:

\begin{itemize}
\item The number of predecessors of A is equal to the number of inputs
  to A, or
\item A has a single predecessor B, and B is also a
  \texttt{phi-instruction} with the same number of inputs as A.
\end{itemize}

In other words, \texttt{phi-instruction}s occur in \emph{clusters}
with the same number of inputs $n$.  The first instruction of such a
cluster has $n$ predecessors, and the others have a single
predecessor. 

Special care must be taken when the graph is modified so that this
restriction is respected. 

Some transformations may be easier to accomplish if there is a single
\texttt{phi-instruction} as opposed to a cluster of several such
instructions.  We may propose a \emph{cluster/uncluster}
transformation on the entire program so that both representations are
accessible. 

\subsection{Instruction \texttt{use-instruction}}
\label{hir-instruction-use}

\begin{tabular}{|l|l|}
\hline
Number of inputs &  1\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction is similar to the \texttt{nop-instruction} in that it
does nothing.  The difference is that this instruction takes a single
input, which is a lexical variable.  The purpose is to create an
artificial use for the input so that it will be kept alive until after
this instruction is encountered.  An instance of this instruction
class will typically be emitted when the \texttt{debug} optimization
quality has a high value.

\subsection{Instruction \texttt{typeq-instruction}}
\label{hir-instruction-typeq}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

This instruction has a slot, with initarg \texttt{:value-type} and
reader \texttt{value-type}. It is a \commonlisp{} type specifier.

The first input of this instruction is an object of which the type
is be tested.

The first successor is chosen if and only if the first input is of
the type stored in the instruction.

This instruction is used in a variety of situations:

\begin{itemize}
\item When the source code contains a call to \texttt{typep} with a
  constant type argument, a compiler macro might transform the call to
  a special form that generates this instruction.
\item Some implementations might generate this instruction from the
  special operator \texttt{the}, where the second successor contains a
  call to \texttt{error}.
\item Since type declarations can be seen as implicit use of the
  special operator \texttt{the}, this instruction can be used for type
  declarations as well.
\item The macro \texttt{check-type} might result in this instruction
  being generated, in which case the second successor would contain
  instructions to signal a correctable error.
\end{itemize}

\subsection{Instruction \texttt{the-instruction}}
\label{hir-instruction-the}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 1\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

There is a single slot, usable with initarg \texttt{:value-type} and
reader \texttt{value-type}.

This instruction is similar to the \texttt{typeq-instruction}. It is
different in that it has no operational effect and does not branch.
It exists only to inform the compiler that its input has been declared
to be a particular type.

It is possible for an implementation to enable \emph{safe code} by
transforming this instruction into \texttt{typeq} with an error
branch.

It is possible for an implementation to remove all instances of this
instruction from the instruction graph after type inference has been
completed (or at any time, if there is no type inference).

\subsection{Instruction \texttt{the-values-instruction}}
\label{hir-instruction-the-values}
\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 1\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction has several extra slots, as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:required-types} & \texttt{required-types} & An ordered list of required types for the values.\\
  \hline
  \texttt{:optional-types} & \texttt{optional-types} & An ordered list of \optional types for the values.\\
  \hline
  \texttt{:rest-type} & \texttt{rest-type} & The \rest type for the values.\\
  \hline
\end{tabular}

This instruction is similar to \texttt{the-instruction}, with the
difference that its input is a values location, and that it
represents a values type. It is used only in contexts where a values
location is needed as an input (e.g., \texttt{return-instruction}s).

Like \texttt{cleavir-ast:the-ast}, the type specified does not have
the implicit \rest behavior of \texttt{cl:the}.

\subsection{Instruction \texttt{multiple-to-fixed-instruction}}
\label{hir-instruction-multiple-to-fixed}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 0\\
  \hline
  Number of outputs & any\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction converts the values in the global values location
to zero or more lexical locations. It is used in contexts where a
fixed number of values is expected but an unknown number of values is
provided in the global values location.

If fewer ordinary lexical locations are required than there are values
contained in the global values location, then the remaining values are
ignored. If more ordinary lexical locations are required than there
are values contained in the values location, then the remaining
ordinary lexical locations are assigned the value \texttt{nil}.

The name of this instruction is sometimes abbreviated ``M->F''.

\subsection{Instruction \texttt{fixed-to-multiple-instruction}}
\label{hir-instruction-fixed-to-multiple}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & any\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction converts zero or more lexical locations into values
in the global values location. It is used in context where a fixed
number of values is provided but an unknown number of values is
required, e.g. a lexical variable access (one value) being the return
value of a function (unknown values).

The name of this instruction is sometimes abbreviated ``F->M''.

\subsection{Instruction \texttt{save-values-instruction}}
\label{hir-instruction-save-values}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 0\\
  \hline
  Number of outputs & 1\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction takes the values in the global values location and
saves them to the dynamic environment by creating an entry on top of
the existing dynamic environment.

The single lexical output location holds the value of the augmented
dynamic environment.

This instruction is used for \texttt{multiple-value-prog1} to save the
values returned by the first sub-form of the
\texttt{multiple-value-prog1} form while the remaining body forms are
evaluated.  Once all the body forms have been evaluated, the values
are restored to the global values location by the
\texttt{restore-values-instruction}.

\subsection{Instruction \texttt{restore-values-instruction}}
\label{hir-instruction-restore-values}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 0\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction takes the values stored in the top entry of the
dynamic environment, and stores them in the global values location.

\subsection{Instruction \texttt{initialize-values-instruction}}
\label{hir-instruction-initialize-values}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 0\\
  \hline
  Number of outputs & 1\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction is used for \texttt{multiple-value-call}.  Its single
output is a location holding an arbitrary number of values to pass as
arguments to \texttt{multiple-value-call}.  This instruction
initializes that location to have no values in it.

\subsection{Instruction \texttt{append-values-instruction}}
\label{hir-instruction-append-values}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 0\\
  \hline
  Number of outputs & 1\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction is used for \texttt{multiple-value-call}.  Its single
output is a location holding an arbitrary number of values to pass as
arguments to \texttt{multiple-value-call}.  This instruction
appends the values in the global values location to the location
indicated by the output.

\subsection{Instruction \texttt{multiple-value-call-instruction}}
\label{hir-instruction-multiple-value-call}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 2\\
  \hline
  Number of outputs & 0\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction represents the full generality of
\texttt{cl:multiple-value-call}, i.e. a call where the number of
values in the arguments is not known statically. The first input is a
lexical location holding the function to call.  The second input holds
all the values to be passed as arguments to the callee.  The values
resulting from the call are stored in the global values location.

Because this instruction is more involved than
\texttt{funcall-instruction}, implementations should endeavor to
avoid its use where possible, and convert
\texttt{cl:multiple-value-call} into \texttt{funcall-instruction}s
instead.

\subsection{Instruction \texttt{symbol-value-instruction}}
\label{hir-instruction-symbol-value}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The input to this instruction must be a symbol naming a special
variable.  The output is the value of that special variable.

\subsection{Instruction \texttt{set-symbol-value-instruction}}
\label{hir-instruction-set-symbol-value}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

The first input to this instruction must be a symbol naming a
special variable.  The second input can be any object.  The effect of
the instruction is to replace the current value of the special
variable the second input.

\subsection{Instruction \texttt{box-instruction}}
\label{hir-instruction-box}

\begin{tabular}{|l|l|}
  \hline
  Number of inputs & 1\\
  \hline
  Number of outputs & 1\\
  \hline
  Number of predecessors & any\\
  \hline
  Number of successors & 1\\
  \hline
\end{tabular}

This instruction has one extra slot, usable with initarg
\texttt{:element-type} and accessor \texttt{element-type}.

The input to this instruction must be an unboxed value of the type
specified by the \texttt{element-type} of the instruction.

The output is a boxed value corresponding to the input.

\subsection{Instruction \texttt{unbox-instruction}}
\label{hir-instruction-unbox}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has one extra slot, usable with initarg
\texttt{:element-type} and accessor \texttt{element-type}.

The input to this instruction must be a boxed value of the type
specified by the \texttt{element-type} of the instruction.

The output is an unboxed value corresponding to the input.

\subsection{Instruction \texttt{unwind-instruction}}
\label{hir-instruction-unwind}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 0\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 0\\
\hline
\end{tabular}

This instruction has two additional slots:

\begin{enumerate}
\item \texttt{destination} that can be initialized with
  \texttt{:destination} and accessed with \texttt{destination}.  This
  slot holds a \texttt{catch-instruction} to which the non-local
  control is transferred.
\item \texttt{index} that can be initialized with \texttt{:index} and
  accessed with \texttt{index}.  This slot holds an index,
  corresponding to one of the successors of the
  \texttt{catch-instruction} to which control is transferred.
\end{enumerate}

The result of executing this instruction is to \emph{unwind} the stack
so that the stack frame of the function of the destination is now at
the top of the stack.  Any intervening \texttt{unwind-protect} forms
are executed as a result.

This instruction is emitted as a result of non-local control
transfers.  As an example, consider the following code:

\begin{verbatim}
(block f
  (funcall (lambda (x) (return-from f x)) 10))
\end{verbatim}

In that code, the \texttt{return-from} form results in an
\texttt{unwind-instruction}, effectively removing the invocation of
the anonymous function from the top of the stack.

\subsection{Instruction \texttt{float-add-instruction}}
\label{hir-instruction-float-add}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}.  If the program is \emph{safe}, then control must reach this
instruction only if this restriction is verified.  The output is also
of type unboxed float.

The output is the sum of the two inputs.

\subsection{Instruction \texttt{float-sub-instruction}}
\label{hir-instruction-float-sub}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the difference between the two inputs.

\subsection{Instruction \texttt{float-mul-instruction}}
\label{hir-instruction-float-mul}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the product of the two inputs.

\subsection{Instruction \texttt{float-div-instruction}}
\label{hir-instruction-float-div}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the quotient of the two inputs.

\subsection{Instruction \texttt{float-less-instruction}}
\label{hir-instruction-float-less}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}.

The first successor is chosen if the first input is strictly less than
the second one; otherwise the second successor is chosen. 

\subsection{Instruction \texttt{float-not-greater-instruction}}
\label{hir-instruction-float-not-greater}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 2\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The inputs to this instruction must be of type \emph{unboxed
  float}.

The first successor is chosen if the first input is less than or equal
to the second one; otherwise the second successor is chosen.

\subsection{Instruction \texttt{float-sin-instruction}}
\label{hir-instruction-float-div}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The input to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the sine of the input.

\subsection{Instruction \texttt{float-cos-instruction}}
\label{hir-instruction-float-div}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The input to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the cosine of the input.

\subsection{Instruction \texttt{float-sqrt-instruction}}
\label{hir-instruction-float-div}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction has an additional slot, accessible as follows:

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:subtype} & \texttt{subtype} & The exact subtype of float.\\
  \hline
\end{tabular}

The input to this instruction must be of type \emph{unboxed
  float}. The output is also of type unboxed float.

The output is the square root of the input.

\subsection{Instruction \texttt{create-cell-instruction}}
\label{hir-instruction-create-cell}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 0\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction creates a \emph{cell} to be used as part of the
captured static environment of a closure.  The exact nature of the
cell that is created is not specified.  Most implementations would
probably just return a \texttt{cons} cell since \texttt{cons} cells
already exist.

\subsection{Instruction \texttt{fetch-instruction}}
\label{hir-instruction-fetch}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

This instruction is used when the static environment is represented as
a single vector containing an entry for each closed-over variable.
Such an entry is either a \emph{cell} (with unspecified
representation) if the corresponding variable is modified, or the
entry can be the variable itself if it is not modified.

This instruction takes two inputs.  The first input is a dynamic
lexical location that holds the static environment.  The second input
is an immediate input containing a non-negative integer and which
serves as an index into the static environment.  This instruction has
a single output, which is a dynamic lexical location.

\subsection{Instruction \texttt{read-cell-instruction}}
\label{hir-instruction-read-cell}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 1\\
\hline
Number of outputs & 1\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

Since the structure of a cell holding the value of a closed-over
variable is unspecified, we use this instruction to obtain the value
held in such a cell.

This instruction takes a single input, namely a dynamic lexical
location holding the cell to be read from.  This instruction has a
single output, namely a dynamic lexical location to hold the value of
the variable.

\subsection{Instruction \texttt{write-cell-instruction}}
\label{hir-instruction-write-cell}

\begin{tabular}{|l|l|}
\hline
Number of inputs & 2\\
\hline
Number of outputs & 0\\
\hline
Number of predecessors & any\\
\hline
Number of successors & 1\\
\hline
\end{tabular}

Since the structure of a cell holding the value of a closed-over
variable is unspecified, we use this instruction to write the value
held in such a cell.

This instruction takes two inputs. The first input is a dynamic
lexical location holding the cell to be written to.  The second input
is a constant input or a dynamic lexical input holding the value to
write to the cell.  This instruction has no outputs.

\section{Data}

\subsection{Input \texttt{constant-input}}

This data type corresponds to constants in source code.  It can only
be used as an \emph{input}.

The slot reader \texttt{value} can be used to access the constant. 

\subsection{Location \texttt{lexical-location}}

This data type corresponds to lexical variable in the source code, and
to temporary variables introduced by the compiler.  It can be used
both as an input and as an output.

The slot reader \texttt{name} can be used to access the name of the
variables.  Notice that different lexical locations have different
\emph{identity} (i.e, they are not \texttt{eq}), but several different
lexical locations may have the same name, due to shadowing.

\subsection{Location \texttt{simple-location}}

This data type corresponds is a subtype of \texttt{lexical-location}.
It is used for lexical locations that are referred to within a single
function, so that there is no possible capture.  A location of this
type can be allocated in a register or on the stack.  A temporary
variable introduced by the compiler will always turn into a datum of
this type.

\subsection{Location \texttt{shared-location}}

This data type corresponds is a subtype of \texttt{lexical-location}.
It is used for lexical locations that are referred to from several
function, i.e., for \emph{shared} variables.  A location of this
type can \emph{not} be allocated in a register or on the stack.
Instead, it has to be allocated in the \emph{static runtime
  environment}. 

\section{Operations on intermediate code}

\subsection{Cloning an instruction}

\Defgeneric {clone-instruction} {instruction}

This function creates a copy of \textit{instruction}.

\Defmethod {clone-instruction} {(instruction {\tt instruction})}

The primary method creates an instance of the class of
\textit{instruction}, with the same inputs, outputs and successors
(the lists are not copied). 

Client code must create \texttt{:after} methods to fill in additional
slots. 

\Defun {insert-instruction-before} {new existing}

Insert the instruction \textit{new} before the instruction
\textit{existing}.  After this operation \textit{new} will have
\textit{existing} as its sole successor, and \textit{existing} will
have \textit{new} as its sole predecessor.  For every instruction $p$
that was a predecessor of \textit{existing} before this operation was
executed, after the operation $p$ will be a predecessor of
\textit{new} and \textit{new} will have replaced \textit{existing} as
a successor of $p$.

\Defun {insert-instruction-between} {new existing1 existing2}

Insert the instruction \textit{new} between the instructions
\textit{existing1} and \textit{existing2}, where \textit{existing2} is
a successor of \textit{existing1}.  \textit{existing1} can have any
number of successors and \textit{existing2} can have any number of
predecessors.  \textit{existing1} becomes the sole predecessor of
\textit{new} and \textit{existing2} becomes the sole successor of
\textit{new}.  \textit{new} replaces \textit{existing2} as a successor
of \textit{existing1}, and \textit{existing1} as a predecessor of
\textit{existing2}.

\Defun {insert-instruction-after} {new existing}

Insert \textit{new} after \textit{existing}.  \textit{existing} must
have a single successor.  The effect is to insert \textit{new} between
\textit{existing} and its sole successor.

\Defun {delete-instruction} {instruction}

Delete \textit{instruction}.  \textit{instruction} must have a single
successor.  The sole successor of \textit{instruction} replaces
\textit{instruction} as the successor of every predecessor of
\textit{instruction}.  The predecessors of \textit{instruction} become
the predecessors of the sole successor of \textit{instruction}.

\Defun {bypass-instruction} {new existing}

This function is used to delete unnecessary branches, among other things.
\textit{new} replaces \textit{existing} as a successor of every
predecessor of \textit{existing}. \textit{new} gains all of
\textit{existing}'s predecessors as predecessors.
Instructions dominated by \textit{existing} and not \textit{new} become
unreachable.

%%  LocalWords:  optimizations reachability unsupplied callee runtime
%%  LocalWords:  subtype backend unboxed
